﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingSpace
{
    class insertSort : Sorting
    {
        int[] values;
        public insertSort(int[] values) { this.values = (int[])values.Clone(); }

        public void Sort()
        {
            for (int i = 1; i < values.Length; i++)
            {
                int num = values[i];
                int insPos = binSearch(values, num, 0, i);

                for (int j = i - 1; j >= insPos; j--)
                    values[j + 1] = values[j];
                values[insPos] = num;
            }
        }

        int binSearch(int[] arr, int item, int low, int high)
        {
            if (high <= low)
                return (item > arr[low]) ? (low + 1) : low;

            int mid = (low + high) / 2;

            if (item == arr[mid])
                return mid + 1;

            if (item > arr[mid])
                return binSearch(arr, item, mid + 1, high);
            return binSearch(arr, item, low, mid - 1);
        }

        public int[] getValues() { return this.values; }

        public string getName() { return "Binary sort"; }
    }
}